其他
质数判定的几种方法及性能优化
文章内容
素性测试 (Primality test)
什么是质数?
遍历取模
遍历取模函数式版本
正则表达式法
开方优化
性能比较
素性测试 (Primality test)
什么是质数?
质数(Prime number,又称素数),指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两个正因数的数)。
遍历取模
判断当前整数是否为质数最常规的方法,就是让它与所有小于它的数(且大于1)取模。
const isPrime = num => {
for (let i = 2; i < num; i++)
if (num % i === 0) return false;
return num > 1;
}
const log = n =>{
console.time(n);
console.log(n, isPrime(n));
console.timeEnd(n);
}
[2,3,4,5,6,7,8,9,10,11,197,977,7919,51977,99991,999983,999987,1000000007,12345678911].map(log);
...
10 false
10: 0.025ms
11 true
11: 0.025ms
197 true
197: 0.034ms
977 true
977: 0.063ms
7919 true
7919: 0.362ms
51977 true
51977: 2.624ms
99991 true
99991: 1.359ms
999983 true
999983: 5.989ms
999987 false
999987: 0.024ms
1000000007 true
1000000007: 6007.705ms
12345678911 false
12345678911: 0.046ms
遍历取模函数式版本
可以用数组方法替代for循环。
正则表达式法
1
的个数来实现监测质数的功能的。此正则表达式分成 由”|”分割两部分: /^1?$/
和/^(11+?)\1+$/
。(11+?)
表示至少有两个1,(11+?)\1
中的\1
表示对前面的匹配的引用。\1+
表示前面的(11+?)
出现至少一次,相当于(11+?){2,}
。整个式子的含义为至少出现两次(11+?)。也就是说,所匹配的数可以写成两个大于2的整数的乘积。而?
通过backtrace穷举所有的可能行,从而完成匹配所有的合数。|
连接,不匹配的就只能是质数了。开方优化
以上方案中,遍历取模是适用而比较广的,它能检测到质数相对较大。
质因数(素因数或质因子)在数论里是指能整除给定正整数的质数。除了1以外,两个没有其他共同质因子的正整数称为互质。
1没有质因子。 5只有1个质因子,5本身。(5是质数) 6的质因子是2和3。(6 = 2 × 3) 2、4、8、16等只有1个质因子:2。(2是质数,4 =2²,8 = 2³,如此类推) 10有2个质因子:2和5。(10 = 2 × 5)
性能比较
开方优化>>遍历取模>函数式遍历取模>正则表达式。
参考资料
A wild way to check if a number is prime using a regular expression | by Mark Sauer-Utley | ITNEXT 正则表达式检测质数 | HE Tao Demystifying The Regular Expression That Checks If A Number Is Prime – The Codeumentary
往期推荐